//
// Created by Jisam on 2024年10月28日23:46:47
// Solution of  P3336 [ZJOI2013] 话旧
#include <bits/stdc++.h>
using namespace std;
#define int long long // 定义int为长整型，用于支持更大的整数范围
int mod = 19940417; // 定义模数，用于取模运算
int n, k, maxVal; // 定义变量n（总长度），k（已知点数量），maxVal（函数最大值）

// 快速加法函数，用于在mod下进行加法运算
void add(int &x, int y) { x = (x + y) % mod; }

// 快速读入函数，用于读取整数
inline void read(int &res) {
    res = 0;
    char c = getchar();
    while (c < '0' || c > '9') c = getchar(); // 跳过非数字字符
    while (c >= '0' && c <= '9') res = (res << 1) + (res << 3) + c - 48, c = getchar(); // 读取数字
}

// 快速幂函数，用于计算base的exp次方在mod下的值
inline int qpow(int base, int exp) {
    if (exp == 0) return 1;
    int result = 1;
    while (exp) {
        if (exp & 1) result = result * base % mod; // 奇数次幂，乘以base
        base = base * base % mod; // 平方
        exp >>= 1; // 右移一位
    }
    return result;
}

struct Point { // 定义点结构体
    int x, y;
} points[1000010]; // 定义点数组

// 重载小于运算符，用于排序
bool operator<(Point a, Point b) { return a.x < b.x; }
// 重载等于运算符，用于比较两个点是否相等
bool operator==(Point a, Point b) { return a.x == b.x && a.y == b.y; }

int dp[1000010][2]; // 定义动态规划数组

signed main() {
    read(n); // 读入n
    read(k); // 读入k
    for (int i = 1; i <= k; i++) read(points[i].x), read(points[i].y); // 读入k个点的坐标
    points[++k] = (Point){0, 0}; // 添加点(0,0)
    points[++k] = (Point){n, 0}; // 添加点(n,0)
    sort(&points[1], &points[k + 1]); // 对点进行排序
    k = unique(&points[1], &points[k + 1]) - points - 1; // 去重

    dp[1][1] = 1; // 初始化动态规划数组的第一项为1
    for (int i = 1; i < k; i++) { // 遍历点数组，进行动态规划
        int halfDiff = points[i + 1].x - points[i].x - points[i + 1].y - points[i].y; // 计算半差值
        halfDiff >>= 1; // 右移一位，相当于除以2
        maxVal = max(maxVal, (points[i + 1].x + points[i + 1].y - points[i].x + points[i].y) / 2); // 更新最大值
        // 根据斜率的不同情况，进行状态转移
        if (points[i + 1].y - points[i].y == points[i].x - points[i + 1].x) 
            dp[i + 1][1] = (dp[i][1] + dp[i][0]) % mod; // 斜率为1
        else if (points[i + 1].y - points[i].y == points[i + 1].x - points[i].x) 
            dp[i + 1][0] = (dp[i][0] + (points[i].y ? 0 : dp[i][1])) % mod; // 斜率为-1
        else if (halfDiff < 0) 
            dp[i + 1][1] = dp[i][0]; // 半差值为负，只能下降
        else if (halfDiff == 0) 
            dp[i + 1][0] = (dp[i][1] + dp[i][0]) % mod, dp[i + 1][1] = dp[i][0]; // 半差值为0，可以上升也可以下降
        else {
            int doublePow = qpow(2, halfDiff - 1); // 计算2的halfDiff-1次方
            if (points[i + 1].y) 
                dp[i + 1][0] = (dp[i][1] + 2LL * dp[i][0]) * doublePow % mod; // 有上升空间
            dp[i + 1][1] = (dp[i][1] + 2LL * dp[i][0]) * doublePow % mod; // 无上升空间
        }
        // 更新最大值
        if ((dp[i + 1][1] || points[i + 1].y == 0) && (dp[i][0] || points[i].y == 0))
            maxVal = max(maxVal, (points[i + 1].x + points[i + 1].y - points[i].x + points[i].y) / 2);
    }
    cout << dp[k][1] % mod << " " << maxVal << endl; // 输出结果
    return 0;
}